package 回溯;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 划分为k个相等的子集686.java
 * @createTime 2022年10月25日 19:50:00
 */
public class 划分为k个相等的子集686 {
	public boolean canPartitionKSubsets(int[] nums, int k) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		if (sum % k != 0) {
			return false;
		}
		boolean[] used = new boolean[nums.length];
		int[] bucket = new int[k+1];
		int trget = sum / k;
		return backTrace(nums, k, 0, bucket, used, trget);
	}

	/**
	 * @param nums     传入的数字列表
	 * @param k        符合条件的子数组的位置
	 * @param numIndex 数字索引
	 * @param bucket   桶
	 * @param used     使用情况列表
	 * @param target   目标值
	 */
	public boolean backTrace(int[] nums, int k, int numIndex, int[] bucket, boolean[] used, int target) {
		//满足条件1：如果满了则说明刚好
		if (k == 0) {
			return true;
		}
		//满足条件2：如果当前位置的值等于目标值，进入下一个，
		if (bucket[k] == target) {
			return backTrace(nums, k - 1, 0, bucket, used, target);
		}
		for (int i = numIndex; i < nums.length; i++) {
			//做选择1：没用过
			if (used[i]) {
				continue;
			}
			//做选择2：和小于目标值
			if (bucket[k] + nums[i] > target) {
				continue;
			}
			used[i] = true;
			bucket[k] += nums[i];
			//继续
			if (backTrace(nums,k,i+1,bucket,used,target)){
				return true;
			}
			//撤销选择
			bucket[k]-=nums[i];
			used[i]=false;
		}
		return false;
	}

}
